import java.util.*;

public class HeapTest {
    public int[] elem;
    public int usedSize;
    public HeapTest(){
        this.elem = new int[10];
    }

    public void adjustDown(int parent, int length){
        int child = 2*parent+1;
        while (child < length){
            if(child+1 < length && this.elem[child] < this.elem[child+1]){
                child++;
            }
            if (this.elem[child] > this.elem[parent]){
                int tmp = this.elem[child];
                this.elem[child] = this.elem[parent];
                this.elem[parent] = tmp;
                parent = child;
                child =  2*parent+1;
            }else {
                break;
            }
        }
    }
    //大根堆
    public void createHeap(int[] array){
        for (int i = 0; i < array.length; i++){
            this.elem[i] = array[i];
            this.usedSize++;
        }
        for (int p = (this.usedSize-1-1)/2; p >= 0; p--){
            adjustDown(p,this.usedSize);
        }
    }

    /*入队*/
    public  void  adjustUp(int child){
        int parent = (child-1)/2;
        while (child > 0){
             if (this.elem[child] > this.elem[parent]){
                 int tmp = this.elem[child];
                 this.elem[child] = this.elem[parent];
                 this.elem[parent] = tmp;
                 child = parent;
                 parent = (child-1)/2;
             }else {
                 break;
             }
        }
    }
    public void push(int key){
        if (isFull()){
            this.elem = Arrays.copyOf(this.elem,this.elem.length*2);
        }
        this.elem[this.usedSize] = key;
        this.usedSize++;
        adjustUp(this.usedSize-1);
    }
    public boolean isFull(){
        return this.usedSize == this.elem.length;
    }


    //出队
    public int pop(){
        int ret = this.elem[0];
        int tmp = this.elem[0];
        this.elem[0] = this.elem[usedSize-1];
        this.elem[usedSize-1] = tmp;
        this.usedSize--;
        adjustDown(0,this.usedSize);
        return ret;


    }

    /*
    *   topk问题  找前K个最大的
    * */
    public  void topK(int[] array, int k){
        //1. 建立小堆
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k,new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1-o2;
            }
        });
        /*minHeap.add()
        minHeap.offer()*/
        //Priority中  this.comparator = comparator;
        //offer中   if (comparator.compare(x, (E) e) >= 0)
        //comparator.compare指向了 你重新new的对象参数
        //2.遍历数组，将k个元素放入小堆
        int count = k;
        for (int i = 0; i < array.length; i++) {
            if(count > 0){//当k 小于等于0 结束放入
                minHeap.offer(array[i]);
                count--;
            }else {
                Integer val = minHeap.peek();//查看堆顶元素
                if (array[i] > val){//如果插入数大于堆顶，弹出堆顶，放入插入的
                    minHeap.poll();
                    minHeap.offer(array[i]);
                }
            }
        }

        for(int i =0 ; i < k; i++){
            System.out.println(minHeap.poll());
        }
        //System.out.println(minHeap);
    }

    //堆排  小 -> 大
    public void heapSort(){
        int end = this.usedSize-1;
        while(end > 0){
            int tmp = this.elem[0];
            this.elem[0] = this.elem[end];
            this.elem[end] = tmp;
            adjustDown(0,end);
            end--;
        }
    }


}
